#include <pthread.h>
#include <iostream>
#include <list>
#include <fstream>




int abss(int a)
{
    return (a > 0 ? a : -a);    
}

using namespace std;

//maksymalna ilosc wierzcholkow
const int max_w = 1000;

//tablica list sasiedztwa 
list <int> tablica_sasiedztwa[max_w + 1]; 

//sciezka wynikowa
list <int> q;

//informacja na temat odwiedzonych wierzcholkow
int odwiedzone[max_w+1];

//rekurencyjne przechodzenie grafu
void spojnosc(int v)
{
  odwiedzone[v] = true;

  for(list<int>::iterator i = tablica_sasiedztwa[v].begin(); i != tablica_sasiedztwa[v].end(); i++)
  {
       if(!odwiedzone[*i]) spojnosc(*i);
  }
}

void *pth_spojnosc(void *argumenty)
{
    //sprawdzenie spojnosci
	//cout << ((int *)argumenty)[0];
        //cout << ((int *)argumenty)[1];
    for(int i = 1; i <= ((int *)argumenty)[0]; ++i)
    {
          if(!odwiedzone[i])
          {
               //czy_spojny
	       ((int *)argumenty)[1]++;	 
               spojnosc(i);
          }
    }
	  return NULL;
}

// rekurencyjne wyszukiwanie
void euler(int v)
{
     while(!tablica_sasiedztwa[v].empty())
     {
           //zapamietanie pierwszego elementu listy
           int x = tablica_sasiedztwa[v].front();  
           
           //usuniecie pierwszego elemntu listy (pierwszego konca sciezki)
           tablica_sasiedztwa[v].pop_front();
           
           //wyszukanie drugiego konca sciezki i usuniecie go
           for(list<int>::iterator i = tablica_sasiedztwa[x].begin(); i != tablica_sasiedztwa[x].end(); i++) 
                 if((* i) == v)
                 { 
                       tablica_sasiedztwa[x].erase(i); 
                       break;
                 }
                 
           euler(x);
     }
     //zapamietanie odwiedzanych wierzcholkow
     q.push_front(v);
}

main()
{
  int wierzcholki, polaczenia, typ; 
  
  /*cout << "Ilosc wierzcholkow: ";
  cin >> wierzcholki;
  
  cout << "Ilosc polaczen: "; 
  cin >> polaczenia;

  cout << endl << "Typ polaczen: ";
  cout << "1 - nieskierowane" << " 2 - skierowane " << "?: ";
  cin >> typ;
*/

ifstream wedane("dane", ios::in);
//spr odczytu
if(!wedane){
cerr<<"plik nie moze byc odczytany"<<endl;
exit(1);
}
wedane>>wierzcholki>>polaczenia;
cout<<"wierzcholki "<<wierzcholki<<endl<<"polaczenia"<<polaczenia;
wedane>>typ;
cout<<endl<<"typ "<<typ<<endl;
//wierzcholki = 6;
//polaczenia = 7;

  //wczytanie polaczen  
  cout <<"wczytanie polaczen"<<endl;
  for(int i = 1; i <= polaczenia; i++)
  {
    int koniec_1, koniec_2; 
    cout << "Polaczenie " << i << ": ";
    wedane >> koniec_1 >> koniec_2;
    cout<<koniec_1<<"  "<<koniec_2<<endl;
    tablica_sasiedztwa[koniec_1].push_back(koniec_2);
    
    //jesli graf jest nieskierowany zapisz pierwszy koniec polaczenia 
    if(typ == 1)
    {
           tablica_sasiedztwa[koniec_2].push_back(koniec_1);
    }
  }
  
  int czy_spojny = 0;
  bool test = true;
  int nieparzyste = 0;
  int startowy = -1;
  
  int wejscia[wierzcholki + 1];
  for(int ii=0; ii<wierzcholki+1; ++ii) wejscia[ii] = 0;

  //przypisanie stanu poczatkowego wierzcholkom: nie odwiedzone
  for(int i = 1; i <= wierzcholki; ++i) 
  {
          odwiedzone[i] = false;
  }

  //nowy watek
  pthread_t thread_w1;

  int *t = new int[2];
  //wierzcholki
  t[0] = wierzcholki;
  
  t[1] = czy_spojny;

  pthread_create(&thread_w1, NULL, pth_spojnosc, (void *)t);

  for(int i = 1; i <= wierzcholki; ++i)
  {
          //jesli graf jest nieskierowany: testuje parzystosc wierzcholkow (max 2 nieparzyste)
          if(typ == 1)
          {
                 if(tablica_sasiedztwa[i].size() % 2)
                 {    
                      ++nieparzyste;
                      if(nieparzyste > 2)
                      {
                                      test = false; 
                                      break;
                      }
                 }
          } else // jesli graf jest skierowany: zlicz wejscia dla poszczegolnych wierzcholkow
          {      
                 for(list<int>::iterator l = tablica_sasiedztwa[i].begin(); l != tablica_sasiedztwa[i].end(); l++) 
                                         ++wejscia[* l];
          }
  }

  //join  pthread_join(thread_w1, NULL);
  czy_spojny = t[1];
  
  //jesli graf jest skierowany: kontynuuj sprawdzanie poprawnosci
  if(typ == 2)
  {
         for(int i=1; i<=wierzcholki; ++i)
         {
                 if( abss(tablica_sasiedztwa[i].size() - wejscia[i]) > 1 )
                 {
                     test = false;    
                     break;
                 } else if(tablica_sasiedztwa[i].size() - wejscia[i] == 1 )
                 {
                        startowy = i;       
                 } 
         }
  }
  
  //jesli graf nie jest spojny nie licz sciezki
  if(czy_spojny != 1) 
  {
       test = false;
  }

  cout << endl;
  
  if(typ == 1 && test)
  {
         if(nieparzyste == 0) cout << "Graf nieskierowany zawiera cykl: ";       
         else if(nieparzyste == 2) cout << "Graf nieskierowany zawiera droge: ";
  } 
  else if(typ == 2 && test)
  {
         if(startowy == -1) cout << "Graf skierowany zawiera cykl: ";       
         else cout << "Graf skierowany zawiera droge: ";
  } 
  
  //jesli graf posiada sciezki
  if(test)
  {
    q.clear();
    euler(1);
    for(list<int>::iterator i = q.begin(); i != q.end(); i++)
      cout << (*i) << " ";
  }
  else cout << "brak cyklu, brak drogi";
  
  cout << endl;
}
